//一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n级的台阶总共有多少种跳法。
//答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
//示例 1：
//输入：n = 2
//输出：2
//示例 2：
//输入：n = 7
//输出：21
//示例 3：
//输入：n = 0
//输出：1
//提示：
//0 <= n <= 100

package main

import "fmt"

// 满足斐波那契数列关系
func numWays(n int) int {
	sum := 0 // f(n)
	a := 1   // f(0) =1
	b := 1   // f(1) =1
	if n == 1 || n == 0 {
		return 1
	}

	for i := 1; i < n; i++ {
		sum = (a + b) % 1000000007
		a = b
		b = sum // f(2)=2
	}
	return sum
}

func main() {
	fmt.Println(numWays(4))
}
